Journals
  Publication Years
  Keywords
Search within results Open Search
Please wait a minute...
For Selected: Toggle Thumbnails
Community search method based on motif connectivity
Ming DU, Wanli GU, Junfeng ZHOU, Zhijun WANG
Journal of Computer Applications    2023, 43 (7): 2190-2199.   DOI: 10.11772/j.issn.1001-9081.2022060941
Abstract161)   HTML4)    PDF (2711KB)(70)       Save

The goal of community search is to obtain compact subgraphs containing query vertices from data graphs, and community search is widely used in sociology, biology, and other fields. In view of the fact that the basic connectivity structures of the existing community models based on subgraph connectivity are all completely connected graphs, which cannot meet the needs of users for the diversity of community structures in practical applications, a community search method based on motif connectivity was proposed, including Motif-Connective Community (MCC) model based on motif connectivity and two corresponding community search algorithms — MPCS (Motif-Processed Community Search) algorithm and MP-index based community search algorithm. MCC model was able to help users freely specify the basic connectivity structure of community, and MPCS algorithm was able to be used to solve the search problem of MCC. Furthermore, two pruning optimization techniques were proposed for the motif instance search process and the belonged community judgment process. Finally, the MP-index forest was designed to avoid redundant traversal operations in the process of community search. Experimental results on multiple real datasets show that the pruning optimization can reduce the running time of MPCS algorithm by 60% to 85%, and the efficiency of the community search algorithm based on MP-index forest is improved by two to three orders of magnitude compared with the efficiency of MPCS algorithm added with pruning optimization. It can be seen that the proposed method has practical application values in commodity recommendation, social network and other issues.

Table and Figures | Reference | Related Articles | Metrics